Міністерство освіти Республіки Білорусь
Установа освіти
«Гомельський державний університет
ім. Ф. Скорини »
Математичний факультет
Кафедра МПУ
Розподіл пам'яті
Курсова робота
Виконавець:
Студентка групи М-41 ____________ Кондратенко О.Ю.
Науковий керівник:
Канд. фіз-мат. наук, доцент ____________ Гундарева Т.Є.
Гомель 2007

Зміст
Введення
1 Задача1.Алгорітм Дойча-Шорр-Уейта
2 Завдання 2. Позначка зайнятих осередків пам'яті
3 Задача 3
3.1 Просте і неефективне рішення проблеми
3.2 Стратегія перерозподілу пам'яті
3.3О структурі пам'яті
4 Метод близнюків
4.1 Головна ідея
4.2 Крок 5: Блок даних об'ємом 4: 1, 1, 2, 3, 1, 4, 3, 5, 13, 21, 34, 55
Висновок
Література

Введення

Переважна більшість програмістів - це прикладні програмісти, то є люди які вважають, що виконання написаної програми комп'ютером - це проблема комп'ютера. Зустрівши команду типу a: integer; комп'ютер повинен її обробити, але в чому полягає ця обробка більшість з нас не дуже цікавиться. Ще менше нас цікавить і процес виконання таких команд як a: integer і new (a). Проте інтуїтивно ми всі розуміємо, (навіть якщо не знаємо точно), що за цими командами ховаються досить складні процеси розподілу і перерозподілу оперативної пам'яті.
Особливо складні проблеми управління для так званої динамічної пам'яті. Дійсно, статичні змінні (тобто ті, які описуються після ключового слова var) створюються один раз, у момент запуску програми на виконання і знищуються один раз, у момент закінчення роботи програми. Це означає, що проблеми перерозподілу пам'яті просто не існує, все визначається на початку і вже ніколи не змінюється.
Однак статична пам'ять це не вся пам'ять. Ще існують динамічні змінні, які можна, як створювати, так і знищити в процесі роботи програми.
Отже, які проблеми виникають при роботі з динамічними змінними, як їх вирішувати і навіщо їх вирішувати? Щоб це зрозуміти, зробимо кілька важливих зауважень:
По-перше, на початку роботи програми, доступна область пам'яті представляє собою суцільний порожній масив комірок пам'яті.
По-друге, в момент створення динамічної змінної, необхідна для неї пам'ять шукається в загальній купі (це программістка термін. Його англійський варіант heap), при цьому програма переглядає всю вільну пам'ять до тих пір, поки не виявить перший досить великий шматок вільної пам'яті.
По-третє, У момент знищення динамічної змінної, використовувані під неї комірки просто повертаються в загальну купу і при цьому ніякого перерозподілу пам'яті не відбувається.
З цих трьох зауважень випливає, що в процесі роботи програми, якщо динамічні змінні багаторазово створюються і знищуються, то купа динамічної пам'яті буде представляти собою безладне нагромадження вільних і зайнятих осередків і може навіть трапиться так, що за наявності великого обсягу вільної пам'яті, розмістити дане великого об'єму не вийде. Пояснимо це картинкою:

	Це вся пам'ять
	А це змінна яку потрібно розмістити

У наявній пам'яті, ми бачимо 5 вільних комірок, проте ніде немає два вільних комірок підряд, а отже нашу змінну, що вимагає два осередки розмістити нікуди.
Якщо проблема зрозуміла, то напевно зрозуміло і те, як в принципі з нею потрібно боротися. Потрібно всі вільні комірки об'єднати в один масив вільної пам'яті. Якщо це зробити, то в нашому прикладі пам'ять буде виглядати так:


Ідея на перший погляд дуже проста, але при її реалізації зустрічається ряд проблем, боротьба з якими може виявитися не цілком тривіальною.
Проблема 1.
З кожною зайнятої групою осередків пам'яті пов'язана спеціальна змінна іменована покажчиком. Покажчик містить адресу цієї групи, і якщо ми групу осередків на яку вказує покажчик перемістимо, то вона для даного покажчика виявиться недоступною.
Проблема 2.
Різні групи клітинок, що містять дані можуть бути взаємопов'язаними. Природно, що при перерозподілі пам'яті взаємозв'язку між даними повинні бути збережені. До речі з можливості існування зв'язкових списків даних слід ще одна цікава проблема. Уявіть собі простий зв'язний список складається з двох зв'язаних динамічних змінних:

Покажчик

Група А

Група В

Група С

Група осередків пам'яті А безпосередньо пов'язана з покажчиком, тобто її місце розташування відомо конкретної змінної, чого не можна сказати про групу В і групі С. І щоб їх виявити необхідно пройти по всьому ланцюжку зв'язного списку. А адже зв'язний список може бути безпідставно складний. Наприклад, такий:

А

У

З

Д

			Е

Спроба пошуку зайнятих елементів пам'яті в такому зв'язковому списку обов'язково призведе до зациклення (В, С, Е) якщо не подбає спеціальним чином про обробці таких ситуацій.
Таким чином, ми бачимо, що необхідність перерозподілу пам'яті дійсно є. Це, по-перше. Приклади, наведені вище, показують, що методи такого перерозподілу не зовсім вже тривіальні, а може бути і досить складні. Це, по-друге. Ось цими методами ми далі і займемося.

1 Завдання 1. Алгоритм Дойча-Шорр-Уейта

Дано масив блоків пам'яті. Для кожного блоку існує мітка, що відзначає, вільний блок від даних або зайнятий. Крім того, деякі з блоків мають посилання на інші блоки, тобто масив блоків зайнятих даними представляє собою один чи кілька зв'язкових списків (графів) довільної структури. Необхідно зібрати всі блоки вільні від даних.
У чому буде полягати рішення:
Отже, ми маємо великий масив пам'яті в якому є як порожні блоки, так і вільні. Нам потрібно або скласти список вільних блоків, або список зайнятих. Це взагалі-то ідентичні завдання. Список результат може представляти собою кілька покажчиків містять адреси початку зв'язного списку складається з вільних або навпаки зайнятих осередків. Хоча, нам зараз не настільки важливо, що буде представляти собою даний список, важливо розібратися з тим, як його скласти.
Загальна ідея
Нехай зайнята пам'ять являє собою деяку кількість зв'язкових списків, природно виконавець (як би конкретно він не працював) повинен проходити всі зв'язні списки і для кожного робити наступне (нехай ми складаємо список використаної пам'яті):
1. Перейти в черговий вузол списку.
2. Записати інформацію про вузлі в список використаної пам'яті.
3. Поки список вузлів пов'язаних з даними не вичерпаний виконувати п.1
Цілком, очевидно, що даний алгоритм (а точніше схема алгоритму) має рекурсивний характер. Це означає, що для кожного вузла списку буде створюватися власна копія процедури обробки вузла (занесення інформації в список-результат і перехід на наступні вузли). І тут виникає серйозна
Проблема
Паскаль, при кожному рекурсивному виклику процедури або функції створює активаційних запис, в якому зберігає інформацію про стан даних отриманих в результаті роботи цієї копії процедури / функції. Тобто, скільки буде викликів (а їх буде стільки скільки вузлів має список), стільки буде активаційних записів створено Паскаль-програмою.
Всі активаційні записи зберігаються в спеціальній структурі пам'яті - стеку, розмір якого обмежений, принаймні, загальним об'ємом оперативної пам'яті. А це означає, що при дуже великій довжині оброблюваного зв'язного списку (і до речі не обов'язково розгалужується, а може бути і лінійного) програмі для запам'ятовування проміжних даних може знадобиться більше пам'яті, ніж її витрачено на аналізовані дані. А це означає втрату будь-якого сенсу в обробці.
Гарна ідея
Гарна ідея напрошується сама собою, треба обійтися без рекурсії. Нижче ми розглянемо дві різні завдання. Перше завдання буде про те як боротися зі зв'язковим списком у якому з кожного вузла може бути не більше двох відгалужень. Другим методом ми спробуємо впорається з більш загальним завданням, тобто таким зв'язковим списком у якому з кожного вузла виходить багато покажчиків.
Примітка: Цей матеріал являє собою конспект глави з книги "Структури даних і алгоритми" авторів: Альфред В. Ахо; Джон Е. Хопкрофта; Джеффрі Д. Ульман
Я тільки дозволив собі в деяких місцях вставити додаткові пояснення, бо вважав їх виклад занадто складним. Сподіваюся, мої пояснення не зробили виклад ще менш зрозумілим.
Мої попередні пояснення:
Основним об'єктом оброблюваним алгоритмом є структура складається з двох осередків (left, right) вказують на наступні комірки, осередків даних і осередки містить позначку зайнята осередок або вільна. Тобто ми маємо справу з двійковим деревом. Може здатися, що це всього лише окремий випадок. Однак це не так, якщо згадати, що будь-яку деревоподібну структуру можна перетворити на двійкове дерево. Нижче наведено приклад двох еквівалентних структур даних. Еквівалентних в тому сенсі, що вони містять однакову кількість змістовних даних і мають однакову кількість зв'язків.
Загальна ідея алгоритму така: необхідно запам'ятовувати шлях, по якому йде алгоритм, щоб мати можливість повернутися до осередку джерела. Для цього можна використовувати наявні покажчики left, right а саме той з них який вже використаний для просування вперед. Але так як в різних вузлах може бути різна ситуація з цими покажчиками, то необхідно запам'ятовувати який з них використовується в конкретній клітинці для запам'ятовування шляху назад. В алгоритмі для цього призначено спеціальне поле back.
Таким чином, замість стека активаційних записів можна використовувати поля покажчиків осередку, аналізованої в даний момент, можна використовувати поля покажчиків уздовж цього шляху, які і будуть формувати шлях. Таким чином, кожна клітинка, за винятком останньої, містить або в полі left, чи в полі right покажчик на її попередника - осередок розташовану ближче до осередку source. Ми опишемо алгоритм, що використовує ще одне бітове поле, яке називається back. Поле це має перераховувані тип (L, R) і говорить про те, яке з полів, left або right, вказує на попередника.
Ця процедура, виконуюча нерекурсивний пошук в глибину використовує покажчик current для вказівки на поточний комірці, а покажчик divvious - для вказівки на попередника поточної комірки. Змінна source вказує на клітинку source1, яка містить тільки покажчик у своєму правому полі. До виконання маркування у клітинці source1 значення поля back встановлюємо рівним R, а її праве поле вказує на самого себе. На клітинку на яку зазвичай вказує source1 тепер вказує осередок current, а на source1 вказує divvious. Операція маркування припиняється у тому разі, коли current = divvious, це може статися лише за умови, якщо обидві комірки current і divvious вказують на source1 тобто вже переглянута вся структура.
1. Рух вглиб. Якщо поточна комірка має один або кілька не порожніх покажчиків, то потрібно перейти на перший з них, тобто слідувати вказівником в полі left або, якщо його немає, то вказівником в полі right. Тепер треба перетворити комірку на яку вказує поточна комірка, в нову поточну клітинку, а стару поточну в попередню. Щоб полегшити пошук шляху назад, потрібно зробити так, щоб вказівник, якому ми тільки що слідували, тепер вказував на колишню попередню клітинку. Ці зміни показані на рисунку А.
2. Перемикання. Якщо ми визначили, що осередки, які виходять із поточної комірки, вже всі переглянуті, то звертаємося до поля back попередньої комірки. Якщо його значення дорівнює L, а поле right цього осередку містить ненульовий покажчик на якусь клітинку C, то робимо З поточною осередком, в той час як статус попередньої комірки залишається незмінним. Але значення поля back попередньої встановлюємо рівним R, а лівий покажчик у цьому осередку встановлюємо так, щоб він вказував на колишню поточну клітинку. Щоб відстежити і зберегти шлях від попередньої осередку, назад до осередку source, треба зробити так, щоб вказівник на клітинку С в полі right в попередній комірці тепер вказував туди, куди вказував раніше її лівий покажчик. Ці зміни показані на рис Б.
3. Відхід. Якщо ми визначили, що осередки, які виходять із поточної комірки, вже переглянуті, але значення поля back попередньої комірки дорівнює R або L, а поле right містить атом (атомів автори називають змістовне дане) або нуль покажчик, значить ми вже переглянули всі комірки, які виходять з попередньої комірки. Тоді здійснюється відхід, при якому попередня осередок стає поточною, а наступна осередок вздовж шляху від попередньої до осередку source - нової попередньої осередком. Ці зміни показані на малюнку В
Неважко помітити, що кожен крок, показаний на малюнку, можна розглядати як одночасну циклічну перестановку трьох покажчиків. Щоб виконати ці модифікації покажчиків, використовується процедура rotate
Procedure rotate (var p1, p2, p3: ^ celltype);
Var
Temp: celltype;
Begin
Temp: = p1;
P1: = p2;
P2: = p3;
P3: = temp;
End;
Тепер повернемося до опису нерекурсивний процедури маркування. Для неї можливі два стани: просування вперед, представлене міткою state1 і відхід представлений міткою state2 і відхід представлений міткою state2. Спочатку, а також у тих випадках, коли ми перейшли на новий осередок (або в результаті кроку просування вперед, або в результаті кроку перемикання), ми переходимо в перший стан. У цьому стані ми намагаємося виконати ще один крок просування вперед і "відходимо" або "перемикаємося" лише в тому випадку, якщо опиняємося заблокованими. Можна бути заблокованими з двох причин: (1) осередок до якої тільки, що звернулися, вже позначена, (2) в даній комірці відсутні ненульові покажчики. Опинившись заблокованими, переходимо до другого стан - стан відходу. Перехід у другу стан можливий в тих випадках, коли ми відходимо або коли не можемо залишатися просування вперед, так як опинилися заблокованими. У стані відходу перевіряємо, відійшли чи назад на клітинку source1. Як вже було сказано вище, ми розпізнаємо цю ситуацію по виконанню умови divvious = current; в цьому випадку переходимо в стан 3 (мітка state3), тобто практично закінчили маркування осередків. В іншому випадку приймається рішення або відступити і залишитися в стані відходу, або переключиться і перейти в стан просування вперед.
А) рух вперед

L

Previous

current

На малюнках старі покажчики показані суцільними лініями, а нові пунктирними.
Б) Зміна

R

	divvious
						current

В) Відхід

	divvious
				current

Автори використовують такі позначення: PP - покажчик / покажчик; PA - покажчик / атом і т.д. Крім того можна помітити, що текст записаний нижче, це не цілком Паскаль-програма. Там не все гаразд з оператором повернення з процедури. Наприклад return (false); це автори роблять для спрощення запису. Розуміти цей оператор треба так:
Ім'я функції: = false;
Goto мітка кінця тіла функції.
function blockleft (cell: celltype): boolean;
{Перевіряє, чи є ліве поле атомом або нуль покажчиком}
begin
with cell do
if (pattern = pp) or (pattern = pa) then
if left <> nil then return (false);
return true;
end; {blockleft}
function blockright (cell: celltype): boolean;
{Перевіряє, чи є ліве поле атомом або нуль покажчиком}
begin
with cell do
if (pattern = pp) or (pattern = ap) then
if right <> nil then return (false);
end; {blockright}
function block (cell: celltype): boolean;
{Перевіряє, позначена чи осередок і чи не містить ненульові покажчики}
begin
if (cell.mark = true) or blockleft (cell) and blockright (cell) then
return true
else return false
end; {block}
procedure nrdfs; {позначає осередку, доступні з осередку source}
var
current, divvious: ^ celltype;
begin {ініціалізація}
current: = source1 ^. right; {осередок на яку вказує source1}
divvious: = source1;
source1 ^. back: = r;
source1 ^. right: = source1;
source1 ^. mark: = true;
state1: {Рух вперед}
if block (current ^) then
begin {Підготовка до відходу}
current ^. mark: = true;
goto state2;
end;
else
begin
{Помітити і просунутися вперед}
current ^. mark: = true;
if blockleft (current ^) then
begin
{Проходження правому вказівником}
current ^. back: = r;
rotate (divvious, current, current ^. right);
{Реалізація зміни згідно зі схемою а}
goto state1
end
else
begin
{Проходження лівому вказівником}
current ^. back: = L;
rotate (divvious, current, current ^. left);
{Реалізація зміни згідно зі схемою а}
goto state1;
end;
end;
state2: {Завершення відхід або перемикання}
if divvious = current then goto state3 {завершення}
else if (divviouse ^. back = L) and (not blockright (divvious ^)) then
begin {перемикання}
divvious ^. back: = R;
rotate (divviouse ^. left, current, divviouse ^. right);
{Реалізація змін як на схемі б}
goto state1;
end
else if divvious ^. back = R then {Відхід}
rotate (divvious, divvious ^. right, current)
{Реалізація змін як на схемі у}
else rotate (divvious, divvious ^. left, current);
{Реалізація змін варіант у, але поле left попередньої комірки включено в дорогу}
goto state2
end;
state 3: {Тут необхідно вставити код для зв'язування непозначених осередків у список вільної пам'яті}
end; {nrdfs}

2 Завдання 2. Позначка зайнятих осередків пам'яті
Загальна постановка нашого завдання наступна: після деякої роботи в оперативній пам'яті знаходиться певна кількість зв'язкових списків. Потрібно, якимось чином позначити всі осередки зайняті цими списками. Для спрощення і без особливих втрат, ми можемо покласти, що список один. У минулій лекції ми розглянули ситуацію коли зв'язний список являє собою двійкове дерево. Тема сьогоднішнього розгляду - ситуація коли список являє собою довільну мережеву структуру.

У чому проблема.

Завдання позначки впирається у завдання обходу списку. Якщо ми навчимося обходити зв'язний список, то проблема позначки вирішиться сама собою. Завдання ж обходу довільного списку має тривіальне рішення. А саме, ми можемо в кожному вузлі має деяку кількість покажчиків ВПЕРЕД завести таку кількість покажчиків ТОМУ і лічильник входжень у даний вузол. Наступний алгоритм буде вирішенням завдання:
При входженні в вузол
Якщо є невикористані покажчики ВПЕРЕД
ТО перейти на вузол по черговому вказівником ВПЕРЕД
ІНАКШЕ
Якщо є невикористані покажчики НАЗАД
ТО перейти на вузол по черговому вказівником НАЗАД
Це дуже загальний алгоритм і ми не будемо розглядати його детально, тому що він все одно не годиться через необхідність заводити велику кількість додаткових покажчиків. Згадаймо, що раніше розглянутий алгоритм (алгоритм Дойч) має сенс лише тому, що він вимагає на два покажчики лише одного додаткового поля. А отже проблема полягає в тому, що нам потрібен алгоритм не вимагає великих ресурсів пам'яті для своєї роботи.

Невеликий попередній аналіз

Суть алгоритму Дойча в тому, що в ньому для запам'ятовування шляху назад використовуються вже наявні покажчики і одне маленьке поле back. Дане поле являє собою однозначне двійкове число яких можна закодувати два числові значення або що те ж саме пронумерувати два покажчики, тому алгоритм працює тільки з двійковим деревом. Очевидно, додавання ще одного бітового поля збільшить кількість покажчиків які можна пронумерувати.

Ідея.

Я думаю, що натяк вже зрозумілий. Якщо ми заведемо додаткове поле розміром в один байт, то це дасть нам можливість пронумерувати 256 покажчиків.
Але це звичайно ще не все. Зрозуміло, що кожен з цих покажчиків може вказувати як вперед так і назад (Пам'ятаєте, що кожен з покажчиків використовується як для запам'ятовування шляху вперед так і шляху назад). Виникає важливе питання: як запам'ятати який куди? Для відповіді домовимося про наступне:
По-перше, нехай безліч покажчиків у кожному вузлі впорядковано лінійно (зараз не важливо як саме це здійснюється, важливо, що порядок є і він лінійний)
По-друге, яким-то чином для кожного вузла визначено скільки у нього покажчиків, наприклад для зберігання цієї інформації заведена ще одна змінна.
Алгоритм, як і алгоритм Дойча, повинен уміти дві речі: по-перше запам'ятовувати шлях назад і по-друге, визначати в кожному вузлі покажчик вказує на вузол у який потрібно перейти.

Загальний опис алгоритму.

Для того, щоб мати можливість рухатися по мережі вузлів у двох напрямах потрібно мати два робочих покажчика. Назвемо їх ВПЕРЕД і НАЗАД. Покажчик ВПЕРЕД містить адресу вузла в який необхідно перейти на наступному кроці, а покажчик НАЗАД містить адресу вузла з якого Виконавець вийшов на попередньому кроці. Це означає, що на кожному кроці (в кожному вузлі) потрібно виконати операції визначення цих адрес.
Розглянемо якийсь вузол, назвемо його Поточний. Коли Виконавець зайде в цей вузол перший раз, він повинен буде перейти на вузол чию адресу зберігається в указателе1. Тобто ВПЕРЕД = Указатель1. Зрозуміло, що це перше і останнє використання покажчика Указатель1. Він більше для запам'ятовування шляху вперед не потрібен, а отже його тепер можна використовувати для запам'ятовування шляху назад, для чого можна виконати операцію Указатель1 = НАЗАД.
Коли виконавець зайде в поточний вузол другий раз він теж саме проробить з указателем2. Це виконавець буде проробляти до тих пір, поки є покажчики ВПЕРЕД якими він ще не користувався. А ось додаткове однобайтові полі (назвемо його лічильник) якраз і стане в нагоді для запам'ятовування номери покажчика яким ще не користувалися.
Перед початком роботи проініціалізіруем поле Лічильник всіх вузлів мережі нулями. Потім кожен раз при вході в черговий вузол будемо збільшувати значення лічильника на 1. Тоді його значення буде визначати номер невикористаного покажчика.
Рано чи пізно виконавець витратить всі покажчики і потрапивши в наш поточний вузол в черговий раз виявить, що вперед йти нікуди, а отже потрібно йти назад. Якщо виконавець вперше прийшов до такого висновку, то очевидно шлях назад зберігається в останньому покажчику. Якщо виконавець вже другий раз на даному сайті вирішив йти назад, то адресу його шляху зберігається в передостанньому покажчику і т.д.

Інакше кажучи

Йдучи вперед виконавець використовує всі покажчики вузла послідовно починаючи з першого, заносячи в них адреси з покажчика НАЗАД. Коли виконавець йде назад він використовує покажчики в зворотному порядку. Щодо динаміки зміни лічильника можна сказати, що поки у вузлі є невикористані покажчики вперед, лічильник зростає (+1 на кожному кроці). Коли починається рух назад, лічильник убуває (-1 на кожному кроці).

Аналогія з лабіринтом

Уявіть себе в лабіринті в якому вузлу відповідають кімнати, а покажчики це коридори. Лічильник це деяка дошка на якій ми можемо записувати число і крім того у нас є можливість з'єднувати коридори лініями. Щоб коректно перевірити весь лабіринт ми повинні обійти всі коридори по порядку і на кожному кроці коридор з якого увійшли до кімнати з'єднувати спрямованим відрізком з тим коридором в який збираємося піти. А номер коридору в який йти ми будемо визначати за кількістю написаного на дошці. Коли не залишиться жодного не пройденого коридору, ми починаючи з останнього і до першого будемо виконувати наступне:
1. Вибираємо черговий коридор.
2. Визначаємо, з яким коридором він пов'язаний (покажчик НАЗАД) і йдемо по ньому.

Алгоритм

Тек_узел = Перший вузол
Поки процес не завершений робити
Знайти останній значущий покажчик
Якщо номер покажчика меншого лічильника входжень
Те
Рух вперед
Інакше
Рух назад
Рух вперед
Обчислити номер невикористаного покажчика ВПЕРЕД
Збільшити значення лічильника входжень
Запам'ятати поточний покажчик НАЗАД в знайденому невикористаній покажчику ВПЕРЕД
Покажчик НАЗАД = адресою поточного вузла.
Покажчик на поточний вузол = вказівником з обчисленими номером
Рух назад
Визначити значення покажчика НАЗАД (зберігається в останньому ненульовому покажчику)
Покажчик на поточний вузол = вказівником НАЗАД
Обнулити останній ненульовий покажчик (визначити його як вказує у нікуди)

Опис програми

Для того, щоб зробити програму більш наочною, в ній повністю реалізовані описані механізми, але без використання покажчиків.
В якості мережі використовується масив записів містять масив покажчиків на вузли і лічильник входжень. Додаткове числове поле потрібно тільки для того, щоб якось показати присутність виконавця у вузлі, значення цього поля буде роздруковуватися коли виконавець вперше зайде у вузол. В якості адреси вузла використовується його номер.
program example;
uses crt;
type
rec = record
count: byte; {лічильник входжень}
num: integer; {просто числове поле}
{Масив покажчиків}
uk: array [1 .. 255] of integer;
end;
var
uzel: array [1 .. 100] of rec;
divd_index, tek_index, i, j, n, m, c: integer;
q: boolean;
procedure print;
{Роздруківка значення вузла}
begin
if uzel [tek_index]. num> 0 then
begin
write (uzel [tek_index]. num ,'');
uzel [tek_index]. num: = 0;
{Це для того, щоб не друкувати кілька разів одне і те ж значення}
readkey;
end;
end;
begin
{Створення мережі}
clrscr;
write ('Введіть кількість вузлів мережі -'); read (n);
for i: = 1 to n do
begin
write ('Вузол номер -', i);
write ('Введіть значення вузла -'); read (uzel [i]. num);
{Ініціалізація масиву посилань}
for j: = 1 to 255 do uzel [i]. uk [j]: = 0;
uzel [i]. count: = 0;
write ('Введіть кількість посилань -'); read (m);
for j: = 1 to m do
begin
write ('посилання номер', j ,'=');
read (uzel [i]. uk [j]);
end;
end;
{Проходження мережі. Починаємо роботу з першого вузла}
tek_index: = 1;
repeat
{Пошук останньої посилання містить покажчик}
m: = 1;
while (uzel [tek_index]. uk [m] <> 0) and (m <255) do m: = m +1;
if m = 255 then m: = 0 else m: = m-1;
if uzel [tek_index]. count <m then {Рух вперед}
begin
print;
{Ми починаємо обхід покажчиків починаючи з останнього. Формула приведена нижче обчислює черговий використовуваний покажчик}
m: = m-uzel [tek_index]. count;
uzel [tek_index]. count: = uzel [tek_index]. count +1;
{Циклічна перестановка покажчиків}
c: = tek_index;
tek_index: = uzel [tek_index]. uk [m];
if c> 1 then uzel [c]. uk [m]: = divd_index
else uzel [c]. uk [m]: = 0;
divd_index: = c;
end
else {відхід назад}
begin
print;
if uzel [tek_index]. count> 0
{Якщо лічильник = 0 і тим не менш є потреба піти з поточного вузла тому, то це означає, що в поточному вузлі немає посилань вперед, а отже не було запомненной багато посилань НАЗАД і є тільки одне посилання НАЗАД зберігається безпосередньо в покажчику divd_index. Якщо ж лічильник>; 0 то це означає, що є запомненние покажчики НАЗАД (до речі теж може бути один) і треба знайти перший з неіспользованнних}
then
begin
{Лічильник якраз і показує на перший з невикористаних покажчиків НАЗАД}
m: = uzel [tek_index]. count;
uzel [tek_index]. count: = uzel [tek_index]. count-1;
{Якщо ми використовували черговий покажчик НАЗАД, і не змінимо значення лічильника, то при наступній спробі відходу назад нам буде запропоновано знову той же покажчик} c: = uzel [tek_index]. Uk [m];
uzel [tek_index]. uk [m]: = 0;
{На початку циклу обробки ми шукаємо перший ненульовий покажчик. Тому покажчики які були використані і як покажчики вперед і як покажчики тому потрібно забути інакше вони знову будуть використані}
tek_index: = c;
end
else tek_index: = divd_index;
{Write ('індекс відходу -', tek_index);
delay (1000);}
end;
if tek_index = 1 then
begin
q: = true;
{Це природна умова припинення роботи. Воно стверджує, що робота припинена, якщо ми знаходимося в першому вузлі і в ньому немає ненульових посилань}
for j: = 1 to 255 do
if uzel [1]. uk [j] <> 0 then q: = false;
end;
until q; {Завершення процесу}
end.
А тепер дозвольте запропонувати невелику завдання. Розглянутий вище алгоритм не працює для цілого класу мереж. Представник цього класу намальований нижче. Помилка не в програмі (звичайно в програмі теж може бути є помилки, як сказав, хтось із великих "Жодна програма не працює правильно"), а в алгоритмі. Я не описав якесь дуже важлива вимога до топології мережі. Відразу хочу сказати, що обмежувати топологію деревами буде надто жорстко. Ця програма з мережами в яких є цикли теж вообщем-то справляється
Ще один цікавий приклад нижче. Цю мережу програма проходить досить успішно, але зависає в той момент коли треба б припинити роботу.
Проблема даного прикладу в алгоритмі. Якщо вам вдасться з'ясувати які обмеження я не описав, то ви побачите, що ця мережа повинна проходиться алгоритмом цілком коректно.

3 Задача 3

"Як створити найбільш ефективну структуру вільної пам'яті. Тобто таку структуру яка дозволяла б розміщувати блоки даних з найменшими витратами часу і фізичної пам'яті."
Нам вже відомо, що це не тривіальна проблема. Просто шукати перше-ліпше вільне місце добре тільки коли вся пам'ять вільна (в цьому випадку досить визначити адресу першої вільної комірки). Якщо ж програма працює занадто довго, то пам'ять машини буде представляти собою скоєно безладне нагромадження вільних і зайнятих блоків, при цьому в досить великому обсязі вільної пам'яті цілком може не виявитися блоку достатнього розміру. Звичайно, якщо таке трапиться, ми можемо перерозподілити пам'ять, тобто зібрати всі вільні блоки в одну купу, але як ми вже бачили в попередніх лекціях це робиться досить складними алгоритмами вимагають значного часу на свою роботу і використовують значний обсяг пам'яті. Звідси ясно, що завдання якоїсь організації пам'яті замість ніякої може дати відчутний виграш, якщо в результаті рідше буде виникати необхідність у «зборці сміття».
Для початку розглянемо просте рішення і на ньому спробуємо трохи краще зрозуміти поставлене завдання.

3.1 Просте і неефективне рішення проблеми

Поділимо всю пам'ять на блоки (назвемо їх елементарними) невеликого розміру. Тоді для розміщення блоку даних потрібно знайти стільки вільних елементарних блоків, щоб у сукупності вони мали потрібний об'єм. Чому це рішення неефективно:
§ Якщо блоки будуть маленькими, то ми нічого не виграємо, тому що така організація пам'яті практично не відрізнятиметься від відсутності організації. Крім того, ми навіть програємо так як треба ж ще організувати список для зберігання адрес вільних блоків, якою може займати значний обсяг пам'яті.
§ Якщо блоки будуть великими ми втрат багато пам'яті на розміщення невеликих блоків, так як маленький блок буде використовувати для свого зберігання великий блок не потребуючи значної його частини.
Висновок: Розглянутий приклад говорить про те, що розбиття пам'яті на блоки однакового розміру при наявності різних блоків даних недоцільно. Ідеальне розбиття - це таке розбиття при якому для кожного блоку даних буде елементарний блок точно такого ж розміру. Це звичайно неможливо, але ми повинні хоча б прагне до такого розбиття.

3.2 Стратегія перерозподілу пам'яті

Як би вдало ми не розбили пам'ять на початку роботи комп'ютера, процес появи поганих (дуже маленьких) фрагментів неминучий, а отже є потреба періодично проводити перерозподіл (об'єднувати блоки, розбивати на декілька, переміщати в інше місце) пам'яті. Які можуть бути загальні методи (стратегії).
Найпростіша стратегія: Через якийсь фіксований інтервал часу переглядати всю пам'ять і створювати новий список вільної пам'яті. Такий підхід буде гарний, тільки якщо час виконання нашої програми нас не цікавить, що навряд чи.
Більш ефективна стратегія. Зауважимо для початку, що жодна програма не використовує всю пам'ять одночасно. З цього очевидного твердження випливає інше, менш очевидне, але дуже корисне: існує інтервал часу протягом якого ефективний розподіл пам'яті порушується лише в невеликій області.
А отже всі операції перерозподілу виконуються тільки для дуже невеликої кількості поруч розташованих блоків пам'яті.
Інакше кажучи
Якщо ми говоримо, що потрібно зайнятися перерозподілом пам'яті, то це означає, що десь завелося кілька поспіль йдуть маленьких блоків, які є сенс об'єднати в один великий або навпаки виникла потреба в розбитті одного великого блоку на декілька більш дрібних.
Важливий висновок
Стратегія управління пам'яттю, це спосіб розбиття та об'єднання блоків пам'яті дозволяє зберігати якусь певну структуру вільної пам'яті.

3.3 Про структуру пам'яті

Перш ніж починати розмову про методи організації пам'яті потрібно сформулювати більш точно, що ми хотіли б від цього виграти. Термін "Ефективна організація" сам по собі не несе ніякої інформації. Я вважаю, що нам потрібно три речі:
1. Пошук вільного блоку потрібного розміру повинен відбуватися як можна швидше.
2. Вільний блок пам'яті призначений для розміщення в ньому блоку даних повинен за розміром як можна точніше відповідати цьому блоку.
3. Перерозподіл пам'яті не має захоплювати велику кількість блоків. Оптимальний варіант - це коли в процесі перерозподілу бере участь не більше двох блоків. Тобто або один блок розбивається на два, або два блоки об'єднуються в один.
Висновки:
По-перше, програма може мати справу з блоками даних самого різного розміру, з цього випливає, що в списку вільних блоків повинні існувати блоки самого різного розміру.
По-друге, для того, щоб пошук здійснювався як можна швидше список блоків повинен бути як то впорядкований, наприклад за зростанням розмірів блоків.
По-третє, розміри блоків бажано визначати за яким-небудь правилом. Це дозволить отримати додатковий виграш у швидкості при пошуку, так як знання правила визначення розміру дозволить хоча б приблизно припустити де в списку вільних блоків знаходиться блок потрібного розміру.

4 Метод близнюків

4.1 Головна ідея

Головна ідея, що лежить в основі методів близнюків, полягає в тому, що всі блоки мають лише строго певні розміри s ₁ <s ₂ <s ₂ <... ... <s _n. (Список блоків впорядкований за зростанням) Характерними варіантами послідовності чисел s _1, s ₂ ... є числа 1,2, 4, 8 ... .. (Метод близнюків експоненціального типу) та 1, 2, 3, 5, 8, 13 .... (Метод близнюків з числами Фіббоначі). Можливі й інші послідовності. Єдиною вимогою до послідовності є простота рахунку. Чергове число в послідовності має бути обраховується як можна меншою кількістю арифметичних операцій. Розмір блоку визначається за формулою V _i = A * s _i де а - кількість байт в найменшому блоці.

Як шукається порожній блок пам'яті для блоку даних

Всі порожні блоки розміру s _i пов'язані в список; крім того, існує масив заголовків списків вільних блоків, по одному для кожного допустимого розміру s _i. Якщо для нового елемента даних потрібно блок розміром d, то вибирається вільний блок такого розміру s _i, щоб s _i> d, проте s _{i -1} <d, тобто найменший допустимий розмір в якому вміщується новий елемент даних. Під найменшим розміром звичайно розуміється такий розмір який не набагато більше блоку даних. Таких величин як «не набагато» звичайно не буває, тому потрібно для конкретного алгоритму точно визначати величину похибки на яку розмір блоку пам'яті може відрізнятися від розміру блоку даних.

Що робити коли потрібного блоку немає

Труднощі виникають у тому випадку, коли не виявляється порожніх блоків необхідного розміру s _i. У цьому випадку знаходиться блок розміром s _{i +1} та розщеплюється на два блоки розміром s _i і s _{i +1-s i.}
Блок s _i це блок потрібного розміру. Після створення потрібного блоку у нас з'являється новий блок, розмір якого повинен бути членом ряду, тобто величина s _{i +1-s i} має дорівнювати деякому числу s _j з використовуваної послідовності, j <i.
Зі сказаного вже може бути ясно, чому в методі близнюків ряд чисел експонентний. У такому ряді числа ростуть дуже швидко, тому в загальну суму ряду найбільший внесок вносять невелику кількість членів ряду, або інакше кажучи невеликих чисел істотно більше ніж більших. Це відповідає ситуації з блоками даних, більшість яких також має невеликий розмір. Крім того, такий ряд буде як би сам підлаштовуватися під реальну ситуацію з блоками даних.
Розглянемо приклад. Нехай ми маємо спочатку наступний ряд: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, тобто ряд побудований на числах Фіббоначі. І є такі блоки даних: 1, 2, 1, 4, 4, 1. Подивимося як будуть розподілятися наші блоки і що буде відбуватися з пам'яттю. Зайняті блоки будемо позначати червоним, а нові блоки синім.
Крок 1: Блок даних об'ємом 1: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
Крок 2: Блок даних об'ємом 2: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
Крок 3: Блок даних об'ємом 1: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
Крок 4: Блок даних об'ємом 4: 1, 1, 2, 3, 1, 4, 8, 13, 21, 34, 55

4.2 Крок 5: Блок даних об'ємом 4: 1, 1, 2, 3, 1, 4, 3, 5, 13, 21, 34, 55

На цьому кроці ми маємо невеликі втрати. А саме довелося використовувати блок довжини 5 для зберігання блоку даних довжини 4
Крок 6: Блок даних об'ємом 1: 1, 1, 2, 3, 1, 4, 3, 5, 13, 21, 34, 55
Не важко помітити, що кількість блоків невеликого розміру збільшилася. А тепер спробуємо оцінити втрати. Розглянемо ще один приклад і на ньому розрахуємо відношення зайнятої пам'яті реальними даними до пам'яті яку довелося викреслити та списку вільної пам'яті. Нехай необхідно розмістити такі блоки: 4,1, 6,7. Загальна пам'ять 1, 1, 2, 3, 5, 8, 13,
Блок 4: 1, 1, 2, 3, 5, 8, 13
Блок 1: 1, 1, 2, 3, 5, 8, 13
Блок 6: 1, 1, 2, 3, 5, 8, 13
Блок 7: 1, 1, 2, 3, 5, 8, 5, 8
Отже отримуємо
Ставлення = 18/22 = 0,82 Це свого роду ККД (коефіцієнт корисної дії)
Звичайно дивлячись з чим порівнювати. Якщо порівняти з двигунами внутрішнього згоряння, то це дуже високий ККД.

Чому розмір блоку залишку повинен бути членом ряду

Уявімо собі процес пошуку блоку потрібного розміру. Нехай у ряду розмірів немає ніяких закономірностей. Тоді все, що нам залишається це чесно переглянути весь ряд, а блок потрібного розміру цілком може опинитися в самому кінці це ряду. Або навіть ще гірша ситуація: блок приблизно відповідного розміру знайшовся вже на самому початку, однак поки ми не переглянемо весь ряд не можна абсолютно впевнено сказати, що немає кращого варіанту. Тому єдиною можливістю закінчити процес пошуку достроково - це виявлення ідеального варіанту, тобто такого блоку пам'яті розмір якого абсолютно точно дорівнює розміру блока даних, а це подія малоймовірно.
Якщо ж ряд розмірів вільних блоків підпорядковується добре рахованої закономірності, то ми маємо відразу два зручності.
По-перше, ми можемо обчислити з деякою точністю номер блоку потрібного розміру. Причому деякий час це обчислення можна виконувати абсолютно точно, і лише коли почнеться процес розбиття великих блоків на маленькі точні обчислення буде виконувати дещо складніше.
По-друге, перший же знайдений блок і буде оптимальним рішенням (бо як наступний буде вже більше і може бути навіть істотно більше).

Висновок

Усі міркування, наведені вище потрібні тільки для того, щоб сформулювати проблеми та окреслити шляхи їх вирішення. А от нижче ми займемося конкретним методом, званим методом близнюків. Цей метод дає відповідь на наступні питання:
1. Як розбити пам'ять на блоки різного розміру, так щоб для будь-якого блоку даних знайшовся потрібний обсяг пам'яті.
2. Як упорядкувати блоки вільної пам'яті, так щоб пошук потрібного блоку вівся максимально швидко.
3. Як організувати швидкий перерозподіл пам'яті так, щоб не було потреби переробляти всю пам'ять і складати новий список вільних блоків.

Література
1. Вострикова З.П. та ін "Програмування на мові" БЕЙСІК "для персональних ЕОМ". Машинобудування, 1993р.
2. Гохман А.В. та ін "Збірник задач з математичної логіки і алгебри множин", видавництво Саратовського Університету, 1969р.
3. Гусєв В.В. Основи імпульсної техніки. М. Радянське радіо, 1975
4. Касаткін В.М. "Інформація, алгоритми, ЕОМ", М. Освіта, 1991р.
5. Машовця В.А. Вступні іспити з інформатики / / Інформатика. 1997, № 13
6. Орлов В.О. Про вступні іспити з інформатики / / Інформатика, 1997, № 15
7. Яснева Г.Г. Логічні основи ЕОМ / / Інформатика та освіта, 1998, № 2
8. Лискова В.Ю., Ракітіна Є.А. Логіка в інформатиці, М. Інформатика та освіта 1999
9. Шауцкова Л.З. "Рішення логічних задач засобами алгебри логіки", газета Інформатика 1999, № 5.